package com.gorkr.labuladong.data_struct.linked_list;

/**
 * @author gorkr
 * @date 2022/06/05 17:34
 **/
public class E92ReverseLinkedListII {
    private ListNode successor = null;

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==1){
            return reverse(head,right);
        }
        head.next = reverseBetween(head.next, left-1, right);

        return head;
    }

    /**
     * 反转从0 到 end 之间的节点
     * @param head 头
     * @param end 末尾下标志
     * @return 反转后的头节点
     */

    // 1->reverse(2->3->4)->5->6
    private ListNode reverse(ListNode head, int end){
        // baseline
        if(end==1){
            successor = head.next;
            return head;
        }
        ListNode last = reverse(head.next,end-1);
        head.next.next = head;
        head.next = successor;
        return last;
    }

}
    